package 头条;

public class 头条机试2dp方法 {
    public static void main(String[] args) {
        int[] a = {6, 3, 1};
        func(a);
    }

    //时间O(n^2) 空间O(n^2)
    private static void func(int[] a) {
        int[][] min = new int[a.length][a.length];
        int[][] sum = new int[a.length][a.length];
        int res = Integer.MIN_VALUE;
        for (int i = 0; i < a.length; i++) {
            for (int j = i; j < a.length; j++) {
                if (i == j) {
                    min[i][j] = a[i];
                    sum[i][j] = a[i];
                    res = Math.max(res, min[i][j] * sum[i][j]);
                } else {
                    min[i][j] = Math.min(min[i][j - 1], a[j]);
                    sum[i][j] = sum[i][j - 1] + a[j];
                    res = Math.max(res, min[i][j] * sum[i][j]);
                }
            }
        }
        System.out.println(res);
    }
}
